Rainbow-independent Set

In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.

Formally, let be a graph, and suppose vertex set is partitioned into subsets , called "colors". A set of vertices is called a rainbow-independent set if it satisfies both the following conditions:

* It is an independent set – every two vertices in are not adjacent (there is no edge between them);
* It is a rainbow set – contains at most a single vertex from each color .

Other terms used in the literature are independent set of representatives, independent transversal, and independent system of representatives.

As an example application, consider a faculty with departments, where some faculty members dislike each other. The dean wants to construct a committee with members, one member per department, but without any pair of members who dislike each other. This problem can be presented as finding an ISR in a graph in which the nodes are the faculty members, the edges describe the "dislike" relations, and the subsets are the departments.

Variants

It is assumed for convenience that the sets are pairwise-disjoint. In general the sets may intersect, but this case can be easily reduced to the case of disjoint sets: for every vertex , form a copy of for each such that contains . In the resulting graph, connect all copies of to each other. In the new graph, the are disjoint, and each ISR corresponds to an ISR in the original graph.

ISR generalizes the concept of a '' system of distinct representatives'' (SDR, also known as transversal). Every transversal is an ISR where in the underlying graph, all and only copies of the same vertex from different sets are connected.

Existence of rainbow-independent sets

There are various sufficient conditions for the existence of an ISR.

Condition based on vertex degree

Intuitively, when the departments are larger, and there is less conflict between faculty members, an ISR should be more likely to exist. The "less conflict" condition is represented by the vertex degree of the graph. This is formalized by the following theorem:

If the degree of every vertex in is at most , and the size of each color-set is at least , then has an ISR.

The is best possible: there are graph with vertex degree and colors of size without an ISR. But there is a more precise version in which the bound depends both on and on .

Condition based on dominating sets

Below, given a subset of colors (a subset of ), we denote by the union of all subsets in (all vertices whose color is one of the colors in ), and by the subgraph of induced by . The following theorem describes the structure of graphs that have no ISR but are ''edge-minimal'', in the sense that whenever any edge is removed from them, the remaining graph has an ISR.

If has no ISR, but for every edge in , has an ISR, then for every edge in , there exists a subset of the colors and a set of edges of , such that:

* The vertices and are both in ;
* The edge is in ;
* The set of vertices adjacent to ''dominates'' ;
* ;
* is a matching – no two edges of it are adjacent to the same vertex.

Hall-type condition

Below, given a subset of colors (a subset of ), an independent set of is called special for if for every independent subset of vertices of of size at most , there exists some in such that is also independent. Figuratively, is a team of "neutral members" for the set of departments, that can augment any sufficiently small set of non-conflicting members, to create a larger such set. The following theorem is analogous to Hall's marriage theorem:

If, for every subset S of colors, the graph contains an independent set that is special for , then has an ISR.

''Proof idea''. The theorem is proved using Sperner's lemma. The standard simplex with endpoints is assigned a triangulation with some special properties. Each endpoint of the simplex is associated with the color-set , each face of the simplex is associated with a set of colors. Each point of the triangulation is labeled with a vertex of such that: (a) For each point on a face , is an element of – the special independent set of . (b) If points and are adjacent in the 1-skeleton of the triangulation, then and are not adjacent in . By Sperner's lemma, there exists a sub-simplex in which, for each point , belongs to a different color-set; the set of these is an ISR.

The above theorem implies Hall's marriage condition. To see this, it is useful to state the theorem for the special case in which is the line graph of some other graph ; this means that every vertex of is an edge of , and every independent set of is a matching in . The vertex-coloring of corresponds to an edge-coloring of , and a rainbow-independent-set in corresponds to a rainbow-matching in . A matching in is special for , if for every matching in of size at most , there is an edge in such that is still a matching in .

Let be a graph with an edge-coloring. If, for every subset of colors, the graph contains a matching that is special for , then has a rainbow-matching.

Let be a bipartite graph satisfying Hall's condition. For each vertex of , assign a unique color to all edges of adjacent to . For every subset of colors, Hall's condition implies that has at least neighbors in , and therefore there are at least edges of adjacent to distinct vertices of . Let be a set of such edges. For any matching of size at most in , some element of has a different endpoint in than all elements of , and thus is also a matching, so is special for . The above theorem implies that has a rainbow matching . By definition of the colors, is a perfect matching in .

Another corollary of the above theorem is the following condition, which involves both vertex degree and cycle length:

If the degree of every vertex in is at most 2, and the length of each cycle of is divisible by 3, and the size of each color-set is at least 3, then has an ISR.

''Proof.'' For every subset of colors, the graph contains at least vertices, and it is a union of cycles of length divisible by 3 and paths. Let be an independent set in containing every third vertex in each cycle and each path. So contains at least vertices. Let be an independent set in of size at most . Since the distance between each two vertices of is at least 3, every vertex of is adjacent to at most one vertex of . Therefore, there is at least one vertex of which is not adjacent to any vertex of . Therefore is special for . By the previous theorem, has an ISR.

Condition based on homological connectivity

One family of conditions is based on the homological connectivity of the independence complex of subgraphs. To state the conditions, the following notation is used:

* denotes the independence complex of a graph (that is, the abstract simplicial complex whose faces are the independent sets in ).
* denotes the homological connectivity of a simplicial complex (i.e., the largest integer such that the first homology groups of are trivial), plus 2.
* is the set of indices of colors, For any subset of , is the union of colors for in .
* is the subgraph of induced by the vertices in .

The following condition is implicit in and proved explicitly in.

If, for all subsets of :
:\eta_H(\text(G _J) \geq , J,
then the partition admits an ISR.

As an example, suppose is a bipartite graph, and its parts are exactly and . In this case so there are four options for :

* then and and the connectivity is infinite, so the condition holds trivially.
* then is a graph with vertices and no edges. Here all vertex sets are independent, so is the power set of , i.e., it has a single -simplex (and all its subsets). It is known that a single simplex is -connected for all integers , since all its reduced homology groups are trivial (see simplicial homology). Hence the condition holds.
* this case is analogous to the previous one.
* then , and contains two simplices and (and all their subsets). The condition is equivalent to the condition that the homological connectivity of is at least 0, which is equivalent to the condition that $\tilde(\text(G))$ is the trivial group. This holds if-and-only-if the complex contains a connection between its two simplices and . Such a connection is equivalent to an independent set in which one vertex is from and one is from . Thus, in this case, the condition of the theorem is not only sufficient but also necessary.

Other conditions

Every properly coloured triangle-free graph of chromatic number contains a rainbow-independent set of size at least .

Several authors have studied conditions for existence of large rainbow-independent sets in various classes of graphs.

Computation

The ''ISR decision problem'' is the problem of deciding whether a given graph and a given partition of into colors admits a rainbow-independent set. This problem is NP-complete. The proof is by reduction from the 3-dimensional matching problem (3DM). The input to 3DM is a tripartite hypergraph , where , , are vertex-sets of size , and is a set of triplets, each of which contains a single vertex of each of , , . An input to 3DM can be converted into an input to ISR as follows:

* For each edge in , there is a vertex in ;
* For each vertex in , let
* For each , , , , , there is an edge in ;
* For each , , , , , there is an edge in ;

In the resulting graph , an ISR corresponds to a set of triplets such that:

* Each triplet has a different value (since each triplet belongs to a different color-set );
* Each triplet has a different value and a different value (since the vertices are independent).

Therefore, the resulting graph admits an ISR if and only if the original hypergraph admits a 3DM.

An alternative proof is by reduction from SAT.

Related concepts

If is the line graph of some other graph , then the independent sets in are the matchings in . Hence, a rainbow-independent set in is a ''rainbow matching'' in . See also matching in hypergraphs.

Another related concept is a ''rainbow cycle'', which is a cycle in which each vertex has a different color.

When an ISR exists, a natural question is whether there exist other ISRs, such that the entire set of vertices is partitioned into disjoint ISRs (assuming the number of vertices in each color is the same). Such a partition is called '' strong coloring''.

Using the faculty metaphor:

* A '' system of distinct representatives'' is a committee of distinct members, with or without conflicts.
* An '' independent set'' is a committee with no conflict.
* An ''independent transversal'' is a committee with no conflict, with exactly one member from each department.
* A ''graph coloring'' is a partitioning of the faculty members into committees with no conflict.
* A '' strong coloring'' is a partitioning of the faculty members into committees with no conflict and with exactly one member from each department. Thus this problem is sometimes called the ''happy dean problem''.
A ''rainbow clique'' or a ''colorful clique'' is a clique in which every vertex has a different color. Every clique in a graph corresponds to an independent set in its complement graph. Therefore, every rainbow clique in a graph corresponds to a rainbow-independent set in its complement graph.

See also

* Graph coloring
* List coloring
* Rainbow coloring
* Rainbow-colorable hypergraph
* Independence complex

References

{{Reflist

Graph theory
Rainbow problems